/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
// class Solution {
// public:
//     void preorder(TreeNode* root, vector<TreeNode*>& v) {
//         if (root == nullptr)
//             return;
//         v.push_back(root);
//         preorder(root->left, v);
//         preorder(root->right, v);
//     }
//     void flatten(TreeNode* root) {
//         if (root == nullptr)
//             return;
//         vector<TreeNode*> v;
//         preorder(root, v);
//         for (int i = 0; i < v.size() - 1; i++) {
//             v[i]->right = v[i + 1];
//             v[i]->left = nullptr;
//         }
//     }
// };
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode* curleft = cur->left;
                TreeNode* curleftRight = curleft;
                while (curleftRight->right) {
                    curleftRight = curleftRight->right;
                }
                curleftRight->right = cur->right;
                cur->right = curleft;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};